package com.yeung.swordoffer;

import java.util.Arrays;

/*
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
例如a b c e
    s f c s
    a d e e 矩阵中包含一条字符串"bcced"的路径，
但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
 */
public class 矩阵中的路径 {
    public static void main(String[] args) {
        char[] matrix = "ABCESFCSADEE".toCharArray();
        int rows = 3, cols = 4;
        char[] str = "ABCCED".toCharArray();
        System.out.println(hasPath(matrix, rows, cols, str));
    }

    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix.length == 0 || rows < 1 || cols < 1 || str.length == 0) return false;
        boolean[] visited = new boolean[matrix.length];
        Arrays.fill(visited, false);
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (pathCore(matrix, rows, cols, row, col, 0, str, visited))
                    return true;
            }
        }
        return false;
    }

    public static boolean pathCore(char[] matrix, int rows, int cols, int row, int col, int pathLength, char[] str, boolean[] visited) {
        if (str.length == pathLength) return true;
        boolean hasPath = false;
        if (enable(rows, cols, row, col, matrix, pathLength, str, visited)) {
            pathLength++;
            visited[row * cols + col] = true;
            hasPath = pathCore(matrix, rows, cols, row, col - 1, pathLength, str, visited) ||
                    pathCore(matrix, rows, cols, row - 1, col, pathLength, str, visited) ||
                    pathCore(matrix, rows, cols, row, col + 1, pathLength, str, visited) ||
                    pathCore(matrix, rows, cols, row + 1, col, pathLength, str, visited);
            if (!hasPath) {//在一个格子的四周没有找到了路径(起点不对)
                pathLength--;//回溯
                visited[row * cols + col] = false;//回到上一次的地方 重新换个方向出发
            }
        }
        return hasPath;
    }

    /**
     * 检查下个格子是否可以添加到路径里
     *
     * @param rows
     * @param cols
     * @param row
     * @param col
     * @param matrix
     * @param pathLength
     * @param str
     * @param visited
     * @return
     */
    public static boolean enable(int rows, int cols, int row, int col, char[] matrix,
                                 int pathLength, char[] str, boolean[] visited) {
        if (row >= 0 && row < rows && col >= 0 && col < cols &&
                matrix[row * cols + col] == str[pathLength] && !visited[row * cols + col])
            return true;
        else
            return false;
    }
}

